#include <iostream>
#include <map>
#include <utility>
using namespace std;

struct ComplexListNode {
  int value;
  ComplexListNode* next;
  ComplexListNode* sibling;
};

ComplexListNode* createNode(int value) {
  ComplexListNode* node = new ComplexListNode();
  node->value = value;
  node->next = nullptr;
  node->sibling = nullptr;
  return node;
}

ComplexListNode* copyComplexList(ComplexListNode* phead) {
  map<ComplexListNode*, ComplexListNode*> node_map;
  auto node = phead;
  ComplexListNode* pre_new_node = nullptr;
  ComplexListNode* ret;
  while (node) {
    auto new_node = new ComplexListNode();
    new_node->value = node->value;
    node_map.insert(make_pair(node, new_node));
    if (pre_new_node)
      pre_new_node->next = new_node;
    else
      ret = new_node;
    pre_new_node = new_node;
    node = node->next;
  }

  node = phead;
  while (node) {
    if (node->sibling) {
      auto new_node = node_map[node];
      auto sibling_node = node->sibling;
      auto new_sibling = node_map[sibling_node];
      new_node->sibling = new_sibling;
    }
    node = node->next;
  }
  return ret;
}

ComplexListNode* copyComplexList1(ComplexListNode* phead) {
  if (!phead)
    return nullptr;
  auto node = phead;
  while (node) {
    auto new_node = createNode(node->value);
    auto next_node = node->next;
    node->next = new_node;
    new_node->next = next_node;
    node = next_node;
  }
  node = phead;
  while (node) {
    if (node->sibling) {
      node->next->sibling = node->sibling->next;
    }
    node = node->next->next;
  }
  node = phead;
  auto ret = node->next;
  auto new_node = node->next;
  node->next = new_node->next;
  node = node->next;
  while (node) {
    new_node->next = node->next;
    new_node = new_node->next;
    node->next = new_node->next;
    node = node->next;
  }
  return ret;
}

void printComplexList(ComplexListNode* phead) {
  auto node = phead;
  cout << "next node: " << endl;
  while (node) {
    cout << node->value << "-";
    node = node->next;
  }
  node = phead;
  cout << "\nsilbing: " << endl;
  while (node) {
    if (node->sibling) {
      cout << node->value << "---" << node->sibling->value << endl;
    }
    node = node->next;
  }
  cout << endl;
}

int main() {
  ComplexListNode* node1 = createNode(1);
  ComplexListNode* node2 = createNode(2);
  ComplexListNode* node3 = createNode(3);
  ComplexListNode* node4 = createNode(4);
  ComplexListNode* node5 = createNode(5);

  node1->next = node2;
  node2->next = node3;
  node3->next = node4;
  node4->next = node5;

  node1->sibling = node3;
  node2->sibling = node5;
  node4->sibling = node2;
  printComplexList(node1);

  auto head_copy = copyComplexList(node1);
  printComplexList(head_copy);

  auto head_copy1 = copyComplexList1(node1);
  printComplexList(head_copy1);

  return 0;
}
